package com.yang.Offer;

public class Offer10 {
}

// 采用递归肯定可以解决但是 面对较大的数，我们可能会栈溢出 而且会占用大量的空间，以及重复计算太多次
// 所以 我们可以保存住中间变量，比如  f(10) = f(9) + f(8) 我们保存下f(9) 与 f(8)  那么从f(0)开始 每层的数我们都只需要计算一次

class SolutionOffer10 {
    public int fib(int n) {
        if( n <= 0){
            return 0;
        }
        if( n == 1){
            return 1;
        }

        int fibOne = 1;
        int fibTwo = 0;
        int fibN = 0;
        for(int i = 2; i <= n; i++){
            fibN = (fibTwo + fibOne) % 1000000007;
            fibTwo = fibOne;
            fibOne = fibN;
        }
        return fibN;
    }
}
